<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1,user-scalable=no"><title>算法基础 | L哲哲のBlog</title><meta name="keywords" content="菜鸡学习❀,算法,数据结构与算法"><meta name="author" content="Leechee~"><meta name="copyright" content="Leechee~"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="不会啊啊啊啊啊~~~"><meta property="og:type" content="article"><meta property="og:title" content="算法基础"><meta property="og:url" content="https://www.lizheblogs.xyz/2022/03/16/Acwing/index.html"><meta property="og:site_name" content="L哲哲のBlog"><meta property="og:description" content="不会啊啊啊啊啊~~~"><meta property="og:locale" content="zh_CN"><meta property="og:image" content="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp"><meta property="article:published_time" content="2022-03-16T15:21:13.000Z"><meta property="article:modified_time" content="2022-04-04T10:33:35.766Z"><meta property="article:author" content="Leechee~"><meta property="article:tag" content="菜鸡学习❀"><meta property="article:tag" content="算法"><meta property="article:tag" content="数据结构与算法"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp"><link rel="shortcut icon" href="https://npm.elemecdn.com/lz-assets@0.0.3/image/sitepage.png"><link rel="canonical" href="https://www.lizheblogs.xyz/2022/03/16/Acwing/"><link rel="preconnect" href="//cdn.jsdelivr.net"><link rel="preconnect" href="//busuanzi.ibruce.info"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload='this.media="all"'><script>const GLOBAL_CONFIG={root:"/",algolia:void 0,localSearch:{path:"search.xml",languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:{defaultEncoding:2,translateDelay:0,msgToTraditionalChinese:"繁",msgToSimplifiedChinese:"簡"},noticeOutdate:void 0,highlight:{plugin:"highlighjs",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:150},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,post:!1},runtime:"天",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{limitCount:150,languages:{author:"作者: Leechee~",link:"链接: ",source:"来源: L哲哲のBlog",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},lightbox:"mediumZoom",Snackbar:void 0,source:{justifiedGallery:{js:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.js",css:"https://cdn.jsdelivr.net/npm/flickr-justified-gallery@2/dist/fjGallery.min.css"}},isPhotoFigcaption:!1,islazyload:!0,isAnchor:!1}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={title:"算法基础",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2022-04-04 18:33:35"}</script><noscript><style>#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:function(e,t,n){if(0===n)return;const o=864e5*n,a={value:t,expiry:(new Date).getTime()+o};localStorage.setItem(e,JSON.stringify(a))},get:function(e){const t=localStorage.getItem(e);if(!t)return;const n=JSON.parse(t);if(!((new Date).getTime()>n.expiry))return n.value;localStorage.removeItem(e)}},e.getScript=e=>new Promise((t,n)=>{const o=document.createElement("script");o.src=e,o.async=!0,o.onerror=n,o.onload=o.onreadystatechange=function(){const e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(o.onload=o.onreadystatechange=null,t())},document.head.appendChild(o)});const t=saveToLocal.get("aside-status");void 0!==t&&("hide"===t?document.documentElement.classList.add("hide-aside"):document.documentElement.classList.remove("hide-aside"));/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><link rel="stylesheet" href="/css/mycss.css" media="defer" onload='this.media="all"'><script data-pjax defer src="https://unpkg.zhimg.com/echarts@4.7.0/dist/echarts.min.js"></script><script data-pjax defer src="https://cdn.jsdelivr.net/gh/sunchaser-lilu/sunchaser-cdn@master/js/circleMagic.min.js"></script><link rel="stylesheet" href="/css/custom/twikoo_beautify.css" media="defer" onload='this.media="all"'><script src="https://npm.elemecdn.com/akilar-candyassets/js/SAO-Notify.js" async></script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/swiper/swiper-bundle.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Zfour/Butterfly-card-history/baiduhistory/css/main.css"><link rel="stylesheet" href="https://unpkg.zhimg.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://unpkg.zhimg.com/hexo-butterfly-swiper/lib/swiperstyle.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://unpkg.zhimg.com/hexo-butterfly-clock/lib/clock.min.css"><link rel="stylesheet" href="https://npm.elemecdn.com/lz-assets@0.0.3/css/runtime.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/assets/font-awesome-animation.min.css" media="defer" onload='this.media="all"'><link rel="stylesheet" href="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/tag_plugins.css" media="defer" onload='this.media="all"'><script src="https://npm.elemecdn.com/hexo-butterfly-tag-plugins-plus@latest/lib/assets/carousel-touch.js"></script><meta name="generator" content="Hexo 6.0.0"></head><body><a href="javascript:void(0);" onclick="preloader.endLoading()" title="点击跳过动画"><div id="loading-box"><div class="SAO-scene"><div class="SAO-wrap"><div class="SAO-wall SAO-wall-right"></div><div class="SAO-wall SAO-wall-left"></div><div class="SAO-wall SAO-wall-top"></div><div class="SAO-wall SAO-wall-bottom"></div><div class="SAO-wall SAO-wall-back"></div></div><div class="SAO-wrap"><div class="SAO-wall SAO-wall-right"></div><div class="SAO-wall SAO-wall-left"></div><div class="SAO-wall SAO-wall-top"></div><div class="SAO-wall SAO-wall-bottom"></div><div class="SAO-wall SAO-wall-back"></div></div></div></div></a><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://cdn.lixingyong.com/2022/03/20/nyantocat.gif" onerror='onerror=null,src="/img/friend_404.gif"' alt="avatar"></div><div class="site-data is-center"><div class="data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a></div><div class="data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">10</div></a></div><div class="data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">9</div></a></div></div><hr><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i> <span>归档</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-book"></i> <span>文档</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/gallery/"><i class="fa-fw fas fa-images"></i> <span>照片</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-heartbeat"></i> <span>其他</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i> <span>大佬</span></a></li><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-heart"></i> <span>关于</span></a></li></ul></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image:url(https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp)"><nav id="nav"><span id="blog_name"><a id="site-name" onclick="btf.scrollToDest(0,500)" data-title="不会啊啊啊啊啊~~~">算法入门总结</a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i> <span>搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i> <span>首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i> <span>归档</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-book"></i> <span>文档</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/tags/"><i class="fa-fw fas fa-tags"></i> <span>标签</span></a></li><li><a class="site-page child" href="/categories/"><i class="fa-fw fas fa-folder-open"></i> <span>分类</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/gallery/"><i class="fa-fw fas fa-images"></i> <span>照片</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-heartbeat"></i> <span>其他</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/link/"><i class="fa-fw fas fa-link"></i> <span>大佬</span></a></li><li><a class="site-page child" href="/about/"><i class="fa-fw fas fa-heart"></i> <span>关于</span></a></li></ul></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">算法基础</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2022-03-16T15:21:13.000Z" title="发表于 2022-03-16 23:21:13">2022-03-16</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2022-04-04T10:33:35.766Z" title="更新于 2022-04-04 18:33:35">2022-04-04</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%8A%80%E6%9C%AF%E5%B8%96/">技术帖</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%8A%80%E6%9C%AF%E5%B8%96/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">4.1k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>19分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" data-flag-title="算法基础"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>基础算法</p><p><code>scanf(&quot;%[^\n]&quot;,a);</code> 载入space</p><p>[TOC]</p><h1 id="基础"><a href="#基础" class="headerlink" title="基础"></a>基础</h1><h2 id="排序"><a href="#排序" class="headerlink" title="排序"></a>排序</h2><h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><p>1 确定分界点 左 右或者中间<br>2 调整区间 划分成俩部分 大于的和小于的<br>3 递归处理左右俩段<br></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quick_sort</span><span class="params">(<span class="keyword">int</span> q[], <span class="keyword">int</span> l, <span class="keyword">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (l &gt;= r) <span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> i = l - <span class="number">1</span>, j = r + <span class="number">1</span>, x = q[l + r &gt;&gt; <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">while</span> (i &lt; j)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">do</span> i ++ ; <span class="keyword">while</span> (q[i] &lt; x);</span><br><span class="line">        <span class="keyword">do</span> j -- ; <span class="keyword">while</span> (q[j] &gt; x);</span><br><span class="line">        <span class="keyword">if</span> (i &lt; j) <span class="built_in">swap</span>(q[i], q[j]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">quick_sort</span>(q, l, j), <span class="built_in">quick_sort</span>(q, j + <span class="number">1</span>, r);</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><br><strong>求最大值</strong><p></p><p>例:<br><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://i0.hdslb.com/bfs/album/17f1d4f8c7e56194d948cc1b1a6009827b4c7021.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://i0.hdslb.com/bfs/album/fe2f9a1aa4f38dbf589b216a96e3d38ba628e7e1.jpg" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">quickfind</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 前半部分和快排完全相同</span></span><br><span class="line">    <span class="keyword">if</span> (l &gt;= r) <span class="keyword">return</span> a[r];</span><br><span class="line">    <span class="keyword">int</span> i = l - <span class="number">1</span>, j = r + <span class="number">1</span>, x = a[l + r &gt;&gt; <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">while</span> (i &lt; j) &#123;</span><br><span class="line">        <span class="keyword">do</span> i++; <span class="keyword">while</span> (a[i] &lt; x);</span><br><span class="line">        <span class="keyword">do</span> j--; <span class="keyword">while</span> (a[j] &gt; x);</span><br><span class="line">        <span class="keyword">if</span> (i &lt; j) <span class="built_in">swap</span>(a[i], a[j]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 求出 SL 的长度（分界点 - 左边界 + 1）</span></span><br><span class="line">    <span class="keyword">int</span> SL = j - l + <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 情况 A</span></span><br><span class="line">    <span class="keyword">if</span> (k &lt;= SL) <span class="keyword">return</span> <span class="built_in">quickfind</span>(l, j, k);</span><br><span class="line">    <span class="comment">// 情况 B</span></span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">return</span> <span class="built_in">quickfind</span>(j + <span class="number">1</span>, r, k - SL);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><p>主要思想:分治 (双指针算法)</p><p>1.找分界点(中间) mid=(l+r&gt;&gt;1)递归排序左右</p><p>2.归并 把俩个有序的数组合并※</p><p><code>分开后有俩个序列,首先递归将俩个序列各自排序,排序完之后分别有一个指针指向俩个序列的最小值,以第一个序列开始的话,对比俩个序列的值哪一个小,小的就放在新建的res数组里去,然后第一个序列的指针往后移动一位(当俩个数字相同时,随便将一个指针后移).重复,直到一个序列的指针在结尾,那么把另一个序列的数全部放在res后面去即可.</code></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge_sort</span><span class="params">(<span class="keyword">int</span> q[], <span class="keyword">int</span> l, <span class="keyword">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (l &gt;= r) <span class="keyword">return</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> mid = l + r &gt;&gt; <span class="number">1</span>;</span><br><span class="line">    <span class="built_in">merge_sort</span>(q, l, mid);</span><br><span class="line">    <span class="built_in">merge_sort</span>(q, mid + <span class="number">1</span>, r);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> k = <span class="number">0</span>, i = l, j = mid + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (i &lt;= mid &amp;&amp; j &lt;= r)</span><br><span class="line">        <span class="keyword">if</span> (q[i] &lt;= q[j]) tmp[k ++ ] = q[i ++ ];</span><br><span class="line">        <span class="keyword">else</span> tmp[k ++ ] = q[j ++ ];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (i &lt;= mid) tmp[k ++ ] = q[i ++ ];</span><br><span class="line">    <span class="keyword">while</span> (j &lt;= r) tmp[k ++ ] = q[j ++ ];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (i = l, j = <span class="number">0</span>; i &lt;= r; i ++, j ++ ) q[i] = tmp[j];</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>or</p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge_sort</span><span class="params">(<span class="keyword">int</span> nums[], <span class="keyword">int</span> left, <span class="keyword">int</span> right)</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (left &gt;= right) <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">int</span> mid = left + ((right - left) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">    <span class="built_in">merge_sort</span>(nums, left, mid);</span><br><span class="line">    <span class="built_in">merge_sort</span>(nums, mid + <span class="number">1</span>, right);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> k = left, l = left, r = mid + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (k &lt;= right) </span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> ((r &gt; right) || (l &lt;= mid &amp;&amp; nums[l] &lt;= nums[r])) tmp[k++] = nums[l++];</span><br><span class="line">        <span class="keyword">else</span> tmp[k++] = nums[r++];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = left; i &lt;= right; ++i) nums[i] = tmp[i];</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="二分"><a href="#二分" class="headerlink" title="二分"></a>二分</h2><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">bsearch</span><span class="params">(<span class="keyword">int</span> l,<span class="keyword">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"><span class="keyword">while</span>(l&lt;=r)</span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">int</span> mid = l+r &gt;&gt;<span class="number">1</span>;</span><br><span class="line"><span class="keyword">if</span>(<span class="built_in">chekc</span>(mid))r=mid<span class="number">-1</span>;</span><br><span class="line"><span class="keyword">else</span> l = mid + <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">return</span> l - <span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="整数"><a href="#整数" class="headerlink" title="整数"></a>整数</h3><h3 id="浮点数"><a href="#浮点数" class="headerlink" title="浮点数"></a>浮点数</h3><h2 id="高精度"><a href="#高精度" class="headerlink" title="高精度"></a>高精度</h2><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="comment">// 高精度加法 a,b均为非负整数,下同</span></span><br><span class="line"><span class="function">string <span class="title">add</span><span class="params">(string a,string b)</span> </span>&#123;</span><br><span class="line">    string c;</span><br><span class="line">    <span class="keyword">int</span> i = a.<span class="built_in">size</span>()<span class="number">-1</span>,j = b.<span class="built_in">size</span>()<span class="number">-1</span>,t = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&gt;=<span class="number">0</span>||j&gt;=<span class="number">0</span>||t!=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span>(i&gt;=<span class="number">0</span>) t += a[i--]-<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(j&gt;=<span class="number">0</span>) t += b[j--]-<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        c += t%<span class="number">10</span>+<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        t/=<span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">string</span>(c.<span class="built_in">rbegin</span>(),c.<span class="built_in">rend</span>());<span class="comment">// or reverse(c.begin(),c.end());</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 高精度减法</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">cmp</span><span class="params">(string a,string b)</span></span>;</span><br><span class="line"><span class="function">string <span class="title">sub</span><span class="params">(string a,string b)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">cmp</span>(a,b)==<span class="number">0</span>) <span class="keyword">return</span> <span class="string">&quot;0&quot;</span>;</span><br><span class="line">    <span class="keyword">if</span>(<span class="built_in">cmp</span>(a,b)==<span class="number">-1</span>) &#123;</span><br><span class="line">        cout&lt;&lt;<span class="string">&quot;-&quot;</span>;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">sub</span>(b,a);</span><br><span class="line">    &#125;</span><br><span class="line">    string c;</span><br><span class="line">    <span class="keyword">int</span> i = a.<span class="built_in">size</span>()<span class="number">-1</span>,j = b.<span class="built_in">size</span>()<span class="number">-1</span>,t = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&gt;=<span class="number">0</span>||j&gt;=<span class="number">0</span>||t!=<span class="number">0</span>) &#123;</span><br><span class="line">        t = a[i--] - t - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(j&gt;=<span class="number">0</span>) t-=b[j--] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        c += (t+<span class="number">10</span>)%<span class="number">10</span> + <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        t = t&lt;<span class="number">0</span>? <span class="number">1</span>: <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(c.<span class="built_in">size</span>()&gt;<span class="number">1</span>&amp;&amp;*c.<span class="built_in">rbegin</span>()==<span class="string">&#x27;0&#x27;</span>) c.<span class="built_in">erase</span>(c.<span class="built_in">size</span>()<span class="number">-1</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">string</span>(c.<span class="built_in">rbegin</span>(),c.<span class="built_in">rend</span>());</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 高精度乘法</span></span><br><span class="line"><span class="function">string <span class="title">mul</span><span class="params">(string a,<span class="keyword">int</span> b)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(a==<span class="string">&quot;0&quot;</span>||b==<span class="number">0</span>) <span class="keyword">return</span> <span class="string">&quot;0&quot;</span>;</span><br><span class="line">    string c;</span><br><span class="line">    <span class="keyword">int</span> i = a.<span class="built_in">size</span>()<span class="number">-1</span>,t = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&gt;=<span class="number">0</span>||t!=<span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">if</span>(i&gt;=<span class="number">0</span>) t+= (a[i--]-<span class="string">&#x27;0&#x27;</span>)*b;</span><br><span class="line">        c += t%<span class="number">10</span>+<span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        t/=<span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">string</span>(c.<span class="built_in">rbegin</span>(),c.<span class="built_in">rend</span>());</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 高精度除法</span></span><br><span class="line"><span class="function">string <span class="title">div</span><span class="params">(string a, <span class="keyword">int</span> b, <span class="keyword">int</span>&amp; r)</span> </span>&#123;</span><br><span class="line">    string c;</span><br><span class="line">    r = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.<span class="built_in">size</span>(); i++) &#123;</span><br><span class="line">        r = r * <span class="number">10</span> + a[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        c += r / b + <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">        r %= b;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (c.<span class="built_in">size</span>() &gt; <span class="number">1</span> &amp;&amp; c[<span class="number">0</span>] == <span class="string">&#x27;0&#x27;</span>) c.<span class="built_in">erase</span>(<span class="number">0</span>, <span class="number">1</span>);</span><br><span class="line">    <span class="keyword">return</span> c;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">cmp</span><span class="params">(string a,string b)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a==b?<span class="number">0</span>:a.<span class="built_in">size</span>()&gt;b.<span class="built_in">size</span>()?<span class="number">1</span>:a.<span class="built_in">size</span>()&lt;b.<span class="built_in">size</span>()?<span class="number">-1</span>:a&gt;b?<span class="number">1</span>:<span class="number">-1</span>; <span class="comment">// 这句话和下面注释内容等价</span></span><br><span class="line">    <span class="comment">// if(a==b) return 0;</span></span><br><span class="line">    <span class="comment">// if(a.size()&gt;b.size()) return 1;</span></span><br><span class="line">    <span class="comment">// if(a.size()&lt;b.size()) return -1;</span></span><br><span class="line">    <span class="comment">// return a&gt;b? 1 : -1;</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="前缀和与差分"><a href="#前缀和与差分" class="headerlink" title="前缀和与差分"></a>前缀和与差分</h2><h3 id="前缀和"><a href="#前缀和" class="headerlink" title="前缀和"></a>前缀和</h3><p><strong>一维</strong></p><p><code>前缀和类似于高中的数组,在求数组前n项和,n~m项和的时候,我们可以使用Sn(前n项和的方式去求出我们所需要部分的长度)</code></p><p><code>S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]</code></p><p><strong>二维</strong></p><p><code>意思同一维 代表求一个面积内某个坐标所对应点的面积</code></p><p><code>S[i, j] = 第i行j列格子左上部分所有元素的和 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]</code></p><h3 id="差分"><a href="#差分" class="headerlink" title="差分"></a>差分</h3><p><strong>-一维-二维</strong></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://i0.hdslb.com/bfs/album/fedd83b37088c87dadc1738166f1f32314690503.png" alt=""></p><h2 id="双指针算法"><a href="#双指针算法" class="headerlink" title="双指针算法"></a>双指针算法</h2><h2 id="位运算"><a href="#位运算" class="headerlink" title="位运算"></a>位运算</h2><h2 id="离散化"><a href="#离散化" class="headerlink" title="离散化"></a>离散化</h2><p>补</p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">vector&lt;<span class="keyword">int</span>&gt; alls; <span class="comment">// 存储所有待离散化的值</span></span><br><span class="line"><span class="built_in">sort</span>(alls.<span class="built_in">begin</span>(), alls.<span class="built_in">end</span>()); <span class="comment">// 将所有值排序</span></span><br><span class="line">alls.<span class="built_in">erase</span>(<span class="built_in">unique</span>(alls.<span class="built_in">begin</span>(), alls.<span class="built_in">end</span>()), alls.<span class="built_in">end</span>());   <span class="comment">// 去掉重复元素</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 二分求出x对应的离散化的值</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span> <span class="comment">// 找到第一个大于等于x的位置</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> l = <span class="number">0</span>, r = alls.<span class="built_in">size</span>() - <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (l &lt; r)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> mid = l + r &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">if</span> (alls[mid] &gt;= x) r = mid;</span><br><span class="line">        <span class="keyword">else</span> l = mid + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> r + <span class="number">1</span>; <span class="comment">// 映射到1, 2, ...n</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="区间合并"><a href="#区间合并" class="headerlink" title="区间合并"></a>区间合并</h2><h1 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h1><h2 id="链表与邻接表-树与图的存储"><a href="#链表与邻接表-树与图的存储" class="headerlink" title="链表与邻接表:树与图的存储"></a>链表与邻接表:树与图的存储</h2><h2 id="栈和队列"><a href="#栈和队列" class="headerlink" title="栈和队列"></a>栈和队列</h2><h2 id="kmp"><a href="#kmp" class="headerlink" title="kmp"></a>kmp</h2><h2 id="Trie树"><a href="#Trie树" class="headerlink" title="Trie树"></a>Trie树</h2><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320114715.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="keyword">int</span> son[N][<span class="number">26</span>], cnt[N], idx;</span><br><span class="line"><span class="comment">// 0号点既是根节点，又是空节点</span></span><br><span class="line"><span class="comment">// son[][]存储树中每个节点的子节点</span></span><br><span class="line"><span class="comment">// cnt[]存储以每个节点结尾的单词数量</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 插入一个字符串</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">char</span> *str)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> p = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; str[i]; i ++ )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> u = str[i] - <span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span> (!son[p][u]) son[p][u] = ++ idx;</span><br><span class="line">        p = son[p][u];</span><br><span class="line">    &#125;</span><br><span class="line">    cnt[p] ++ ;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 查询字符串出现的次数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">char</span> *str)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> p = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; str[i]; i ++ )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> u = str[i] - <span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span> (!son[p][u]) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        p = son[p][u];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> cnt[p];</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h2><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320153552.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">(<span class="number">1</span>)朴素并查集：</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> p[N]; <span class="comment">//存储每个点的祖宗节点</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回x的祖宗节点</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p[x] != x) p[x] = <span class="built_in">find</span>(p[x]);</span><br><span class="line">        <span class="keyword">return</span> p[x];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 初始化，假定节点编号是1~n</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ ) p[i] = i;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 合并a和b所在的两个集合：</span></span><br><span class="line">    p[<span class="built_in">find</span>(a)] = <span class="built_in">find</span>(b);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">(<span class="number">2</span>)维护size的并查集：</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> p[N], size[N];</span><br><span class="line">    <span class="comment">//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回x的祖宗节点</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p[x] != x) p[x] = <span class="built_in">find</span>(p[x]);</span><br><span class="line">        <span class="keyword">return</span> p[x];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 初始化，假定节点编号是1~n</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">    &#123;</span><br><span class="line">        p[i] = i;</span><br><span class="line">        size[i] = <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 合并a和b所在的两个集合：</span></span><br><span class="line">    size[<span class="built_in">find</span>(b)] += size[<span class="built_in">find</span>(a)];</span><br><span class="line">    p[<span class="built_in">find</span>(a)] = <span class="built_in">find</span>(b);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">(<span class="number">3</span>)维护到祖宗节点距离的并查集：</span><br><span class="line"></span><br><span class="line">    <span class="keyword">int</span> p[N], d[N];</span><br><span class="line">    <span class="comment">//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离</span></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 返回x的祖宗节点</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (p[x] != x)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">int</span> u = <span class="built_in">find</span>(p[x]);</span><br><span class="line">            d[x] += d[p[x]];</span><br><span class="line">            p[x] = u;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> p[x];</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 初始化，假定节点编号是1~n</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">    &#123;</span><br><span class="line">        p[i] = i;</span><br><span class="line">        d[i] = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 合并a和b所在的两个集合：</span></span><br><span class="line">    p[<span class="built_in">find</span>(a)] = <span class="built_in">find</span>(b);</span><br><span class="line">    d[<span class="built_in">find</span>(a)] = distance; <span class="comment">// 根据具体问题，初始化find(a)的偏移量</span></span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h2><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="comment">// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1</span></span><br><span class="line"><span class="comment">// ph[k]存储第k个插入的点在堆中的位置</span></span><br><span class="line"><span class="comment">// hp[k]存储堆中下标是k的点是第几个插入的</span></span><br><span class="line"><span class="keyword">int</span> h[N], ph[N], hp[N], size;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 交换两个点，及其映射关系</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">heap_swap</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">swap</span>(ph[hp[a]],ph[hp[b]]);</span><br><span class="line">    <span class="built_in">swap</span>(hp[a], hp[b]);</span><br><span class="line">    <span class="built_in">swap</span>(h[a], h[b]);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">down</span><span class="params">(<span class="keyword">int</span> u)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> t = u;</span><br><span class="line">    <span class="keyword">if</span> (u * <span class="number">2</span> &lt;= size &amp;&amp; h[u * <span class="number">2</span>] &lt; h[t]) t = u * <span class="number">2</span>;</span><br><span class="line">    <span class="keyword">if</span> (u * <span class="number">2</span> + <span class="number">1</span> &lt;= size &amp;&amp; h[u * <span class="number">2</span> + <span class="number">1</span>] &lt; h[t]) t = u * <span class="number">2</span> + <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">if</span> (u != t)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">heap_swap</span>(u, t);</span><br><span class="line">        <span class="built_in">down</span>(t);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">up</span><span class="params">(<span class="keyword">int</span> u)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">while</span> (u / <span class="number">2</span> &amp;&amp; h[u] &lt; h[u / <span class="number">2</span>])</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">heap_swap</span>(u, u / <span class="number">2</span>);</span><br><span class="line">        u &gt;&gt;= <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// O(n)建堆</span></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = n / <span class="number">2</span>; i; i -- ) <span class="built_in">down</span>(i);</span><br><span class="line"></span><br></pre></td></tr></table></figure><h2 id="Hash表"><a href="#Hash表" class="headerlink" title="Hash表"></a>Hash表</h2><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320171935.png" alt=""></p><p>模拟散列表</p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">(<span class="number">1</span>) 拉链法</span><br><span class="line">    <span class="keyword">int</span> h[N], e[N], ne[N], idx;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 向哈希表中插入一个数</span></span><br><span class="line">    <span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> k = (x % N + N) % N;</span><br><span class="line">        e[idx] = x;</span><br><span class="line">        ne[idx] = h[k];</span><br><span class="line">        h[k] = idx ++ ;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 在哈希表中查询某个数是否存在</span></span><br><span class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> k = (x % N + N) % N;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = h[k]; i != <span class="number">-1</span>; i = ne[i])</span><br><span class="line">            <span class="keyword">if</span> (e[i] == x)</span><br><span class="line">                <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">(<span class="number">2</span>) 开放寻址法</span><br><span class="line">    <span class="keyword">int</span> h[N];</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置</span></span><br><span class="line">    <span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> t = (x % N + N) % N;</span><br><span class="line">        <span class="keyword">while</span> (h[t] != null &amp;&amp; h[t] != x)</span><br><span class="line">        &#123;</span><br><span class="line">            t ++ ;</span><br><span class="line">            <span class="keyword">if</span> (t == N) t = <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> t;</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure><h3 id="字符串哈希"><a href="#字符串哈希" class="headerlink" title="字符串哈希"></a>字符串哈希</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320180401.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320173908.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">核心思想：将字符串看成P进制数，P的经验值是<span class="number">131</span>或<span class="number">13331</span>，取这两个值的冲突概率低</span><br><span class="line">小技巧：取模的数用<span class="number">2</span>^<span class="number">64</span>，这样直接用<span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span>存储，溢出的结果就是取模的结果</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">unsigned</span> <span class="keyword">long</span> <span class="keyword">long</span> ULL;</span><br><span class="line">ULL h[N], p[N]; <span class="comment">// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64</span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 初始化</span></span><br><span class="line">p[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">&#123;</span><br><span class="line">    h[i] = h[i - <span class="number">1</span>] * P + str[i];</span><br><span class="line">    p[i] = p[i - <span class="number">1</span>] * P;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 计算子串 str[l ~ r] 的哈希值</span></span><br><span class="line"><span class="function">ULL <span class="title">get</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> h[r] - h[l - <span class="number">1</span>] * p[r - l + <span class="number">1</span>];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="STL技巧"><a href="#STL技巧" class="headerlink" title="STL技巧"></a>STL技巧</h2><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">vector, 变长数组，倍增的思想</span><br><span class="line">    <span class="built_in">size</span>()  返回元素个数</span><br><span class="line">    <span class="built_in">empty</span>()  返回是否为空</span><br><span class="line">    <span class="built_in">clear</span>()  清空</span><br><span class="line">    <span class="built_in">front</span>()/<span class="built_in">back</span>()</span><br><span class="line">    <span class="built_in">push_back</span>()/<span class="built_in">pop_back</span>()</span><br><span class="line">    <span class="built_in">begin</span>()/<span class="built_in">end</span>()</span><br><span class="line">    []</span><br><span class="line">    支持比较运算，按字典序</span><br><span class="line"></span><br><span class="line">pair&lt;<span class="keyword">int</span>, string&gt;</span><br><span class="line">    p=<span class="built_in">make_pair</span>(x,xx);<span class="comment">//可以是数字也可以是字符串</span></span><br><span class="line">	pair&lt;<span class="keyword">int</span> , pair&lt;<span class="keyword">int</span> , <span class="keyword">int</span>&gt;&gt;p;</span><br><span class="line">    first, 第一个元素</span><br><span class="line">    second, 第二个元素</span><br><span class="line">    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）</span><br><span class="line"></span><br><span class="line">string，字符串</span><br><span class="line">    string a=<span class="string">&quot;lzzzzzz&quot;</span>;</span><br><span class="line">    <span class="built_in">size</span>()/<span class="built_in">length</span>()  返回字符串长度</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">clear</span>()</span><br><span class="line">    <span class="built_in">substr</span>(起始下标，(子串长度))  返回子串</span><br><span class="line">    <span class="built_in">c_str</span>()  返回字符串所在字符数组的起始地址</span><br><span class="line"></span><br><span class="line">queue, 队列</span><br><span class="line">    queue&lt;<span class="keyword">int</span>&gt; q; q=queue&lt;<span class="keyword">int</span>&gt;();</span><br><span class="line">    <span class="built_in">size</span>()</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">push</span>()  向队尾插入一个元素</span><br><span class="line">    <span class="built_in">front</span>()  返回队头元素</span><br><span class="line">    <span class="built_in">back</span>()  返回队尾元素</span><br><span class="line">    <span class="built_in">pop</span>()  弹出队头元素</span><br><span class="line"></span><br><span class="line">priority_queue, 优先队列，默认是大根堆</span><br><span class="line">    priority_queue&lt;<span class="keyword">int</span>&gt; heap;</span><br><span class="line">    <span class="built_in">size</span>()</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">push</span>()  插入一个元素</span><br><span class="line">    <span class="built_in">top</span>()  返回堆顶元素</span><br><span class="line">    <span class="built_in">pop</span>()  弹出堆顶元素</span><br><span class="line">    定义成小根堆的方式：priority_queue&lt;<span class="keyword">int</span>, vector&lt;<span class="keyword">int</span>&gt;, greater&lt;<span class="keyword">int</span>&gt;&gt; q;</span><br><span class="line"></span><br><span class="line">stack, 栈</span><br><span class="line">    <span class="built_in">size</span>()</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">push</span>()  向栈顶插入一个元素</span><br><span class="line">    <span class="built_in">top</span>()  返回栈顶元素</span><br><span class="line">    <span class="built_in">pop</span>()  弹出栈顶元素</span><br><span class="line"></span><br><span class="line">deque, 双端队列</span><br><span class="line">    <span class="built_in">size</span>()</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">clear</span>()</span><br><span class="line">    <span class="built_in">front</span>()/<span class="built_in">back</span>()</span><br><span class="line">    <span class="built_in">push_back</span>()/<span class="built_in">pop_back</span>()</span><br><span class="line">    <span class="built_in">push_front</span>()/<span class="built_in">pop_front</span>()</span><br><span class="line">    <span class="built_in">begin</span>()/<span class="built_in">end</span>()</span><br><span class="line">    [] <span class="comment">//随机选取</span></span><br><span class="line"></span><br><span class="line">set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列</span><br><span class="line">    <span class="built_in">size</span>()</span><br><span class="line">    <span class="built_in">empty</span>()</span><br><span class="line">    <span class="built_in">clear</span>()</span><br><span class="line">    <span class="built_in">begin</span>()/<span class="built_in">end</span>()</span><br><span class="line">    ++, -- 返回前驱(前一个数)和后继，时间复杂度 <span class="built_in">O</span>(logn)</span><br><span class="line"></span><br><span class="line">    set/<span class="function">multiset</span></span><br><span class="line"><span class="function">        <span class="title">insert</span><span class="params">()</span>  插入一个数</span></span><br><span class="line"><span class="function">        <span class="title">find</span><span class="params">()</span>  查找一个数</span></span><br><span class="line"><span class="function">        <span class="title">count</span><span class="params">()</span>  返回某一个数的个数</span></span><br><span class="line"><span class="function">        <span class="title">erase</span><span class="params">()</span></span></span><br><span class="line"><span class="function">            <span class="params">(<span class="number">1</span>)</span> 输入是一个数x，删除所有x   <span class="title">O</span><span class="params">(k + logn)</span></span></span><br><span class="line"><span class="function">            <span class="params">(<span class="number">2</span>)</span> 输入一个迭代器，删除这个迭代器</span></span><br><span class="line"><span class="function">        <span class="title">lower_bound</span><span class="params">()</span>/<span class="title">upper_bound</span><span class="params">()</span></span></span><br><span class="line"><span class="function">            <span class="title">lower_bound</span><span class="params">(x)</span>  返回大于等于x的最小的数的迭代器</span></span><br><span class="line"><span class="function">            <span class="title">upper_bound</span><span class="params">(x)</span>  返回大于x的最小的数的迭代器</span></span><br><span class="line"><span class="function">    map/multimap</span></span><br><span class="line"><span class="function">    exp:map&lt;string,int&gt;a</span></span><br><span class="line"><span class="function">        a[<span class="string">&quot;lzz&quot;</span>]=</span><span class="number">1</span>; cout&lt;&lt;a[<span class="string">&quot;lzz&quot;</span>] -&gt;<span class="number">1</span></span><br><span class="line">        <span class="built_in">insert</span>()  插入的数是一个<span class="function">pair</span></span><br><span class="line"><span class="function">        <span class="title">erase</span><span class="params">()</span>  输入的参数是pair或者迭代器</span></span><br><span class="line"><span class="function">        <span class="title">find</span><span class="params">()</span></span></span><br><span class="line"><span class="function">        []  注意multimap不支持此操作。 时间复杂度是 <span class="title">O</span><span class="params">(logn)</span></span></span><br><span class="line"><span class="function">        <span class="title">lower_bound</span><span class="params">()</span>/<span class="title">upper_bound</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function">unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表</span></span><br><span class="line"><span class="function">    和上面类似，增删改查的时间复杂度是 <span class="title">O</span><span class="params">(<span class="number">1</span>)</span></span></span><br><span class="line"><span class="function">    不支持 <span class="title">lower_bound</span><span class="params">()</span>/<span class="title">upper_bound</span><span class="params">()</span>， 迭代器的++，--</span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function">bitset, 圧位</span></span><br><span class="line"><span class="function">    bitset&lt;10000&gt; s</span>;</span><br><span class="line">    ~, &amp;, |, ^</span><br><span class="line">    &gt;&gt;, &lt;&lt;</span><br><span class="line">    ==, !=</span><br><span class="line">    []</span><br><span class="line"></span><br><span class="line">    <span class="built_in">count</span>()  返回有多少个<span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="built_in">any</span>()  判断是否至少有一个<span class="number">1</span></span><br><span class="line">    <span class="built_in">none</span>()  判断是否全为<span class="number">0</span></span><br><span class="line"></span><br><span class="line">    <span class="built_in">set</span>()  把所有位置成<span class="number">1</span></span><br><span class="line">    <span class="built_in">set</span>(k, v)  将第k位变成v</span><br><span class="line">    <span class="built_in">reset</span>()  把所有位变成<span class="number">0</span></span><br><span class="line">    <span class="built_in">flip</span>()  等价于~</span><br><span class="line">    <span class="built_in">flip</span>(k) 把第k位取反</span><br></pre></td></tr></table></figure><h3 id="vector遍历"><a href="#vector遍历" class="headerlink" title="vector遍历"></a>vector遍历</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220320191604.png" alt=""></p><h1 id="搜索与图论"><a href="#搜索与图论" class="headerlink" title="搜索与图论"></a>搜索与图论</h1><h2 id="DFS与BFS"><a href="#DFS与BFS" class="headerlink" title="DFS与BFS"></a>DFS与BFS</h2><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324031504.png" alt=""></p><h3 id="DFS"><a href="#DFS" class="headerlink" title="DFS"></a>DFS</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220323195446.png" alt=""></p><h4 id="N皇后问题"><a href="#N皇后问题" class="headerlink" title="N皇后问题"></a>N皇后问题</h4><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324013225.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324013309.png" alt=""></p><p><strong>第一种解法dfs</strong></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324013057.png" alt=""></p><h3 id="BFS"><a href="#BFS" class="headerlink" title="BFS"></a>BFS</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324030031.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324031557.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220324031715.png" alt=""></p><h2 id="树与图"><a href="#树与图" class="headerlink" title="树与图"></a>树与图</h2><h3 id="存储"><a href="#存储" class="headerlink" title="存储"></a>存储</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220325005124.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="comment">// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点</span></span><br><span class="line"><span class="keyword">int</span> h[N], e[N], ne[N], idx;</span><br><span class="line"><span class="comment">// n个链表的链表头  结点的值是多少  每个节点的next值是多少  </span></span><br><span class="line"></span><br><span class="line"><span class="comment">// 添加一条边a-&gt;b</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;</span><br><span class="line">    <span class="comment">//</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 初始化</span></span><br><span class="line">idx = <span class="number">0</span>;</span><br><span class="line"><span class="built_in">memset</span>(h, <span class="number">-1</span>, <span class="keyword">sizeof</span> h);</span><br></pre></td></tr></table></figure><h3 id="遍历"><a href="#遍历" class="headerlink" title="遍历"></a>遍历</h3><h4 id="dfs"><a href="#dfs" class="headerlink" title="dfs"></a>dfs</h4><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220325015944.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    st[u] = <span class="literal">true</span>; <span class="comment">// st[u] 表示点u已经被遍历过</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = h[u]; i != <span class="number">-1</span>; i = ne[i])</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> j = e[i];<span class="comment">//当前链表里的节点对应图里的编号</span></span><br><span class="line">        <span class="keyword">if</span> (!st[j]) <span class="built_in">dfs</span>(j);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="bfs"><a href="#bfs" class="headerlink" title="bfs"></a>bfs</h4><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220325022329.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">queue&lt;<span class="keyword">int</span>&gt; q;</span><br><span class="line">st[<span class="number">1</span>] = <span class="literal">true</span>; <span class="comment">// 表示1号点已经被遍历过</span></span><br><span class="line">q.<span class="built_in">push</span>(<span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span> (q.<span class="built_in">size</span>())</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">int</span> t = q.<span class="built_in">front</span>();</span><br><span class="line">    q.<span class="built_in">pop</span>();</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = h[t]; i != <span class="number">-1</span>; i = ne[i])</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> j = e[i];</span><br><span class="line">        <span class="keyword">if</span> (!st[j])</span><br><span class="line">        &#123;</span><br><span class="line">            st[j] = <span class="literal">true</span>; <span class="comment">// 表示点j已经被遍历过</span></span><br><span class="line">            q.<span class="built_in">push</span>(j);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="最短路"><a href="#最短路" class="headerlink" title="最短路"></a>最短路</h2><h2 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h2><h2 id="二分图：染色法、匈牙利算法"><a href="#二分图：染色法、匈牙利算法" class="headerlink" title="二分图：染色法、匈牙利算法"></a>二分图：染色法、匈牙利算法</h2><h1 id="Math"><a href="#Math" class="headerlink" title="Math"></a>Math</h1><h3 id="More"><a href="#More" class="headerlink" title="More"></a>More</h3><p>质数<br>约数<br>欧拉函数<br>快速幂<br>扩展欧几里得算法<br>中国剩余定理<br>高斯消元<br>组合计数<br>容斥原理<br>简单博弈论</p><h1 id="动态规划"><a href="#动态规划" class="headerlink" title="动态规划"></a>动态规划</h1><h2 id="背包问题"><a href="#背包问题" class="headerlink" title="背包问题"></a>背包问题</h2><h3 id="01背包"><a href="#01背包" class="headerlink" title="01背包"></a>01背包</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220325163423.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1010</span>;</span><br><span class="line"><span class="keyword">int</span> n;<span class="comment">//所有物品个数</span></span><br><span class="line"><span class="keyword">int</span> m;<span class="comment">//背包容量</span></span><br><span class="line"><span class="keyword">int</span> v[N], w[N];<span class="comment">//v表示体积,w表示价值</span></span><br><span class="line"><span class="keyword">int</span> f[N][N];<span class="comment">//表示所有的状态</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) cin &gt;&gt; v[i] &gt;&gt; w[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;=n; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= m; j++) &#123;</span><br><span class="line">            f[i][j] = f[i - <span class="number">1</span>][j];</span><br><span class="line">            <span class="keyword">if</span> (j &gt;= v[i]) f[i][j] = <span class="built_in">max</span>(f[i][j], f[i - <span class="number">1</span>][j - v[i]] + w[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    cout &lt;&lt; f[n][m];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//转化成一维</span></span><br><span class="line"><span class="comment">//f(i)只用到了f(i-1)这层 </span></span><br><span class="line"><span class="keyword">int</span> f[N];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    cin &gt;&gt; n &gt;&gt; m;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) cin &gt;&gt; v[i] &gt;&gt; w[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>; i&lt;=n; i++)</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = m; j &gt;= v[i]; j--) &#123;</span><br><span class="line">            f[j] = <span class="built_in">max</span>(f[j], f[j - v[i]] + w[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    cout &lt;&lt; f[m];</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="完全背包"><a href="#完全背包" class="headerlink" title="完全背包"></a>完全背包</h3><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line"><span class="comment">//朴素做法</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1010</span>;</span><br><span class="line"><span class="keyword">int</span> n,m;</span><br><span class="line"><span class="keyword">int</span> v[N],w[N];</span><br><span class="line"><span class="keyword">int</span> f[N][n];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    cin&gt;&gt;n&gt;&gt;m;</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ ) cin &gt; v[i] &gt;&gt;w[i];</span><br><span class="line">    	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;= m; j ++ )</span><br><span class="line">				<span class="keyword">for</span> (<span class="keyword">int</span> k =<span class="number">0</span>; k * v[i] &lt;= j; k ++ )</span><br><span class="line">					f[i][j] = <span class="built_in">max</span>(f[i][j]，f[i - <span class="number">1</span>][j - v[i]* k] + w[i] * k);</span><br><span class="line">	cout &lt;&lt; f[n][m] &lt;&lt; endl;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//优化成二维</span></span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ ) cin &gt; v[i] &gt;&gt;w[i];</span><br><span class="line">    	<span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">			<span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;= m; j ++ )</span><br><span class="line">            &#123;</span><br><span class="line">                f[i][j]=f[i<span class="number">-1</span>][j];</span><br><span class="line">                <span class="keyword">if</span>(j&gt;=v[i])</span><br><span class="line">                    f[i][j]=<span class="built_in">max</span>(f[i][j],f[i][j-v[i]]+w[i]);</span><br><span class="line">            &#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//优化成一维</span></span><br><span class="line"><span class="keyword">int</span> f[N];</span><br><span class="line"><span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i ++ )</span><br><span class="line">		<span class="keyword">for</span> (<span class="keyword">int</span> j = v[i]; j &lt;= m; j ++ )</span><br><span class="line">            &#123;</span><br><span class="line">                    f[j]=<span class="built_in">max</span>(f[j],f[j-v[i]]+w[i]);</span><br><span class="line">            &#125;</span><br></pre></td></tr></table></figure><h3 id="完全背包-1"><a href="#完全背包-1" class="headerlink" title="完全背包"></a>完全背包</h3><p>暴力</p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220325204453.png" alt=""></p><figure class="highlight c++"><table><tr><td class="code"><pre><span class="line">```</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"></span><br><span class="line">## 线性DP</span><br><span class="line"></span><br><span class="line">### 数字三角形</span><br><span class="line"></span><br></pre></td></tr></table></figure><p>给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。</p><pre><code>    7
  3   8
8   1   0
</code></pre><p>2 7 4 4<br>4 5 2 6 5</p><p>输入格式<br>第一行包含整数n，表示数字三角形的层数。</p><p>接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。</p><p>输出格式<br>输出一个整数，表示最大的路径数字和。</p><p>数据范围<br>1 ≤ n ≤ 500,<br>−10000 ≤ 三角形中的整数 ≤ 10000</p><p>输入样例：<br>5<br>7<br>3 8<br>8 1 0<br>2 7 4 4<br>4 5 2 6 5</p><p>输出样例：<br>30</p><p>```</p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220326165232.png" alt=""></p><h3 id="最长上升子序列"><a href="#最长上升子序列" class="headerlink" title="最长上升子序列"></a>最长上升子序列</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220326165740.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220327011837.png" alt=""></p><h2 id="区间DP"><a href="#区间DP" class="headerlink" title="区间DP"></a>区间DP</h2><h3 id="石子合并"><a href="#石子合并" class="headerlink" title="石子合并"></a>石子合并</h3><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220327022354.png" alt=""></p><p><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/loading.gif" data-lazy-src="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/20220327024625.png" alt=""></p><h2 id="计数类DP"><a href="#计数类DP" class="headerlink" title="计数类DP"></a>计数类DP</h2><h2 id="数位统计DP"><a href="#数位统计DP" class="headerlink" title="数位统计DP"></a>数位统计DP</h2><h2 id="状态压缩DP"><a href="#状态压缩DP" class="headerlink" title="状态压缩DP"></a>状态压缩DP</h2><h2 id="树形DP"><a href="#树形DP" class="headerlink" title="树形DP"></a>树形DP</h2><h2 id="记忆化搜索"><a href="#记忆化搜索" class="headerlink" title="记忆化搜索"></a>记忆化搜索</h2><h1 id="贪心"><a href="#贪心" class="headerlink" title="贪心"></a>贪心</h1><h1 id="时空复杂度"><a href="#时空复杂度" class="headerlink" title="时空复杂度"></a>时空复杂度</h1></article><div class="post-copyright"><div class="post-copyright__title"><span class="post-copyright-info"><h>算法基础</h></span></div><div class="post-copyright__type"><span class="post-copyright-info"><a href="https://www.lizheblogs.xyz/2022/03/16/Acwing/">https://www.lizheblogs.xyz/2022/03/16/Acwing/</a></span></div><div class="post-copyright-m"><div class="post-copyright-m-info"><div class="post-copyright-a"><h>作者</h><div class="post-copyright-cc-info"><h>Leechee~</h></div></div><div class="post-copyright-c"><h>发布于</h><div class="post-copyright-cc-info"><h>2022-03-16</h></div></div><div class="post-copyright-u"><h>更新于</h><div class="post-copyright-cc-info"><h>2022-04-04</h></div></div><div class="post-copyright-c"><h>许可协议</h><div class="post-copyright-cc-info"><a class="icon" rel="noopener" target="_blank" title="Creative Commons" href="https://creativecommons.org/"><i class="fab fa-creative-commons"></i></a><a rel="noopener" target="_blank" title="CC BY-NC-SA 4.0" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a></div></div></div></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E8%8F%9C%E9%B8%A1%E5%AD%A6%E4%B9%A0%E2%9D%80/">菜鸡学习❀</a><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a><a class="post-meta__tags" href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></div><div class="post_share"><div class="social-share" data-image="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp" data-sites="qq,wechat,weibo"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2022/03/16/Cplus%E5%9F%BA%E7%A1%80/"><img class="prev-cover" src="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp" onerror='onerror=null,src="/img/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">C++基础</div></div></a></div><div class="next-post pull-right"><a href="/2022/04/01/Linux%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B%E5%9F%BA%E7%A1%80/"><img class="next-cover" src="https://cdn.lixingyong.com/2022/04/03/e449f2921b1439dfa4cdebce3160f27e.webp" onerror='onerror=null,src="/img/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Linux 网络编程基础</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2022/02/01/Cplus%E8%A1%A5%E5%85%85/" title="C++基础再学习"><img class="cover" src="https://cdn.lixingyong.com/2022/03/22/wallhaven-28wqwg_1920x1080.webp" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-02-01</div><div class="title">C++基础再学习</div></div></a></div><div><a href="/2022/02/05/ros%E5%9F%BA%E7%A1%80/" title="ROS1 Noetic"><img class="cover" src="https://cdn.lixingyong.com/2022/04/03/6PIWL626OOBW_KE8FN9.webp" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-02-05</div><div class="title">ROS1 Noetic</div></div></a></div><div><a href="/2022/03/16/Cplus%E5%9F%BA%E7%A1%80/" title="C++基础"><img class="cover" src="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2022-03-16</div><div class="title">C++基础</div></div></a></div></div></div><hr><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i> <span>评论</span></div><div id="comment-switch"><span class="first-comment">Twikoo</span><span class="switch-btn"></span><span class="second-comment">Disqus</span></div></div><div class="comment-wrap"><div><div id="twikoo-wrap"></div></div><div><div id="disqus_thread"></div></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://cdn.lixingyong.com/2022/03/20/nyantocat.gif" onerror='this.onerror=null,this.src="/img/friend_404.gif"' alt="avatar"></div><div class="author-info__name">Leechee~</div><div class="author-info__description">♥</div></div><div class="card-info-data is-center"><div class="card-info-data-item"><a href="/archives/"><div class="headline">文章</div><div class="length-num">8</div></a></div><div class="card-info-data-item"><a href="/tags/"><div class="headline">标签</div><div class="length-num">10</div></a></div><div class="card-info-data-item"><a href="/categories/"><div class="headline">分类</div><div class="length-num">9</div></a></div></div><a id="card-info-btn"><i class="fas fa-check"></i><span>收藏一下吧~</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://qm.qq.com/cgi-bin/qm/qr?k=NCqRvHC5G55ERcHdHHiMVcRcv2Z1tLFq&amp;noverify=0" target="_blank" title="添加我的QQ"><i class="fab fa-qq"></i></a><a class="social-icon" href="https://cdn.jsdelivr.net/gh/zhezheup/picture-house/mmqrcode1642538711409.png" target="_blank" title="添加我的微信"><i class="fab fa-weixin"></i></a><a class="social-icon" href="https://blog.csdn.net/weixin_45824920?spm=1000.2115.3001.5343" target="_blank" title="关注我的CSDN"><i class="far fa-copyright"></i></a><a class="social-icon" href="https://github.com/zhezheup" target="_blank" title="Star我的Github"><i class="fab fa-github"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">建设中......<br></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%9F%BA%E7%A1%80"><span class="toc-number">1.</span> <span class="toc-text">基础</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F"><span class="toc-number">1.1.</span> <span class="toc-text">排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-number">1.1.1.</span> <span class="toc-text">快速排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">1.1.2.</span> <span class="toc-text">归并排序</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86"><span class="toc-number">1.2.</span> <span class="toc-text">二分</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%95%B4%E6%95%B0"><span class="toc-number">1.2.1.</span> <span class="toc-text">整数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%B5%AE%E7%82%B9%E6%95%B0"><span class="toc-number">1.2.2.</span> <span class="toc-text">浮点数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%AB%98%E7%B2%BE%E5%BA%A6"><span class="toc-number">1.3.</span> <span class="toc-text">高精度</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E5%92%8C%E4%B8%8E%E5%B7%AE%E5%88%86"><span class="toc-number">1.4.</span> <span class="toc-text">前缀和与差分</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E5%92%8C"><span class="toc-number">1.4.1.</span> <span class="toc-text">前缀和</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B7%AE%E5%88%86"><span class="toc-number">1.4.2.</span> <span class="toc-text">差分</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8F%8C%E6%8C%87%E9%92%88%E7%AE%97%E6%B3%95"><span class="toc-number">1.5.</span> <span class="toc-text">双指针算法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BD%8D%E8%BF%90%E7%AE%97"><span class="toc-number">1.6.</span> <span class="toc-text">位运算</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%A6%BB%E6%95%A3%E5%8C%96"><span class="toc-number">1.7.</span> <span class="toc-text">离散化</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6"><span class="toc-number">1.8.</span> <span class="toc-text">区间合并</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">2.</span> <span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E4%B8%8E%E9%82%BB%E6%8E%A5%E8%A1%A8-%E6%A0%91%E4%B8%8E%E5%9B%BE%E7%9A%84%E5%AD%98%E5%82%A8"><span class="toc-number">2.1.</span> <span class="toc-text">链表与邻接表:树与图的存储</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97"><span class="toc-number">2.2.</span> <span class="toc-text">栈和队列</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#kmp"><span class="toc-number">2.3.</span> <span class="toc-text">kmp</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Trie%E6%A0%91"><span class="toc-number">2.4.</span> <span class="toc-text">Trie树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="toc-number">2.5.</span> <span class="toc-text">并查集</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A0%86"><span class="toc-number">2.6.</span> <span class="toc-text">堆</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Hash%E8%A1%A8"><span class="toc-number">2.7.</span> <span class="toc-text">Hash表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%93%88%E5%B8%8C"><span class="toc-number">2.7.1.</span> <span class="toc-text">字符串哈希</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#STL%E6%8A%80%E5%B7%A7"><span class="toc-number">2.8.</span> <span class="toc-text">STL技巧</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#vector%E9%81%8D%E5%8E%86"><span class="toc-number">2.8.1.</span> <span class="toc-text">vector遍历</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%90%9C%E7%B4%A2%E4%B8%8E%E5%9B%BE%E8%AE%BA"><span class="toc-number">3.</span> <span class="toc-text">搜索与图论</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#DFS%E4%B8%8EBFS"><span class="toc-number">3.1.</span> <span class="toc-text">DFS与BFS</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#DFS"><span class="toc-number">3.1.1.</span> <span class="toc-text">DFS</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#N%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98"><span class="toc-number">3.1.1.1.</span> <span class="toc-text">N皇后问题</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BFS"><span class="toc-number">3.1.2.</span> <span class="toc-text">BFS</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%91%E4%B8%8E%E5%9B%BE"><span class="toc-number">3.2.</span> <span class="toc-text">树与图</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AD%98%E5%82%A8"><span class="toc-number">3.2.1.</span> <span class="toc-text">存储</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%81%8D%E5%8E%86"><span class="toc-number">3.2.2.</span> <span class="toc-text">遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#dfs"><span class="toc-number">3.2.2.1.</span> <span class="toc-text">dfs</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#bfs"><span class="toc-number">3.2.2.2.</span> <span class="toc-text">bfs</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E7%9F%AD%E8%B7%AF"><span class="toc-number">3.3.</span> <span class="toc-text">最短路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91"><span class="toc-number">3.4.</span> <span class="toc-text">最小生成树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%88%86%E5%9B%BE%EF%BC%9A%E6%9F%93%E8%89%B2%E6%B3%95%E3%80%81%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95"><span class="toc-number">3.5.</span> <span class="toc-text">二分图：染色法、匈牙利算法</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Math"><span class="toc-number">4.</span> <span class="toc-text">Math</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#More"><span class="toc-number">4.0.1.</span> <span class="toc-text">More</span></a></li></ol></li></ol><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-number">5.</span> <span class="toc-text">动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98"><span class="toc-number">5.1.</span> <span class="toc-text">背包问题</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#01%E8%83%8C%E5%8C%85"><span class="toc-number">5.1.1.</span> <span class="toc-text">01背包</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85"><span class="toc-number">5.1.2.</span> <span class="toc-text">完全背包</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85-1"><span class="toc-number">5.1.3.</span> <span class="toc-text">完全背包</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-number">5.1.4.</span> <span class="toc-text">最长上升子序列</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8C%BA%E9%97%B4DP"><span class="toc-number">5.2.</span> <span class="toc-text">区间DP</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%9F%B3%E5%AD%90%E5%90%88%E5%B9%B6"><span class="toc-number">5.2.1.</span> <span class="toc-text">石子合并</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E7%B1%BBDP"><span class="toc-number">5.3.</span> <span class="toc-text">计数类DP</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E4%BD%8D%E7%BB%9F%E8%AE%A1DP"><span class="toc-number">5.4.</span> <span class="toc-text">数位统计DP</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%8A%B6%E6%80%81%E5%8E%8B%E7%BC%A9DP"><span class="toc-number">5.5.</span> <span class="toc-text">状态压缩DP</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%91%E5%BD%A2DP"><span class="toc-number">5.6.</span> <span class="toc-text">树形DP</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2"><span class="toc-number">5.7.</span> <span class="toc-text">记忆化搜索</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E8%B4%AA%E5%BF%83"><span class="toc-number">6.</span> <span class="toc-text">贪心</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%97%B6%E7%A9%BA%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">7.</span> <span class="toc-text">时空复杂度</span></a></li></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/04/01/Linux%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B%E5%9F%BA%E7%A1%80/" title="Linux 网络编程基础"><img src="https://cdn.lixingyong.com/2022/04/03/e449f2921b1439dfa4cdebce3160f27e.webp" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="Linux 网络编程基础"></a><div class="content"><a class="title" href="/2022/04/01/Linux%E7%BD%91%E7%BB%9C%E7%BC%96%E7%A8%8B%E5%9F%BA%E7%A1%80/" title="Linux 网络编程基础">Linux 网络编程基础</a><time datetime="2022-04-01T15:21:13.000Z" title="发表于 2022-04-01 23:21:13">2022-04-01</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/16/Acwing/" title="算法基础"><img src="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="算法基础"></a><div class="content"><a class="title" href="/2022/03/16/Acwing/" title="算法基础">算法基础</a><time datetime="2022-03-16T15:21:13.000Z" title="发表于 2022-03-16 23:21:13">2022-03-16</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/03/16/Cplus%E5%9F%BA%E7%A1%80/" title="C++基础"><img src="https://cdn.lixingyong.com/2022/04/03/img-1644609719397bc9e4fdea5a0db766963cc472d1de411.webp" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="C++基础"></a><div class="content"><a class="title" href="/2022/03/16/Cplus%E5%9F%BA%E7%A1%80/" title="C++基础">C++基础</a><time datetime="2022-03-16T15:21:13.000Z" title="发表于 2022-03-16 23:21:13">2022-03-16</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/13/Ubuntu%E7%BE%8E%E5%8C%96/" title="Ubuntu20.04美化"><img src="https://cdn.lixingyong.com/2022/04/03/zcool.jfif.webp" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="Ubuntu20.04美化"></a><div class="content"><a class="title" href="/2022/02/13/Ubuntu%E7%BE%8E%E5%8C%96/" title="Ubuntu20.04美化">Ubuntu20.04美化</a><time datetime="2022-02-13T15:21:13.000Z" title="发表于 2022-02-13 23:21:13">2022-02-13</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/05/ros%E5%9F%BA%E7%A1%80/" title="ROS1 Noetic"><img src="https://cdn.lixingyong.com/2022/04/03/6PIWL626OOBW_KE8FN9.webp" onerror='this.onerror=null,this.src="/img/404.jpg"' alt="ROS1 Noetic"></a><div class="content"><a class="title" href="/2022/02/05/ros%E5%9F%BA%E7%A1%80/" title="ROS1 Noetic">ROS1 Noetic</a><time datetime="2022-02-05T15:21:13.000Z" title="发表于 2022-02-05 23:21:13">2022-02-05</time></div></div></div></div></div></div></main><footer id="footer" style="background:linear-gradient(135deg,"><div id="footer-wrap"><div class="copyright"><span>&copy;2021 - 2022</span><svg style="width:1.5em;height:1.5em" aria-hidden="true"><use xlink:href="#icon-butterfly"></use></svg><span>Leechee~</span></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button id="sakura_show" type="button" title="打开/关闭-❀樱花"><i class="fas fa-candy-cane"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="chat_btn" type="button" title="在线聊天"><i class="fas fa-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">本地搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i> <span>数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/medium-zoom/dist/medium-zoom.min.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script src="https://cdn.jsdelivr.net/npm/vanilla-lazyload/dist/lazyload.iife.min.js"></script><script src="/js/search/local-search.js"></script><script async>var preloader={endLoading:()=>{document.body.style.overflow="auto",document.getElementById("loading-box").classList.add("loaded")},initLoading:()=>{document.body.style.overflow="",document.getElementById("loading-box").classList.remove("loaded")}};window.addEventListener("load",preloader.endLoading()),setTimeout((function(){preloader.endLoading()}),4e3)</script><div class="js-pjax"><script>(()=>{const e=document.querySelectorAll("#article-container .mermaid-wrap");if(e.length){window.runMermaid=()=>{window.loadMermaid=!0;const t="dark"===document.documentElement.getAttribute("data-theme")?"dark":"default";Array.from(e).forEach((e,n)=>{const d=e.firstElementChild,r="mermaid-"+n,i="%%{init:{ 'theme':'"+t+"'}}%%\n"+d.textContent;mermaid.mermaidAPI.render(r,i,e=>{d.insertAdjacentHTML("afterend",e)})})};const t=()=>{window.loadMermaid?runMermaid():getScript("https://cdn.jsdelivr.net/npm/mermaid/dist/mermaid.min.js").then(runMermaid)};window.pjax?t():document.addEventListener("DOMContentLoaded",t)}})()</script><script>(()=>{const t=()=>{twikoo.init(Object.assign({el:"#twikoo-wrap",envId:"https://twikoo-phi-lime.vercel.app/",region:"ap-xian-ec",onCommentLoaded:function(){btf.loadLightbox(document.querySelectorAll("#twikoo .tk-content img:not(.vemoji)"))}},null))},o=()=>{"object"!=typeof twikoo?getScript("https://cdn.jsdelivr.net/npm/twikoo/dist/twikoo.all.min.js").then(t):setTimeout(t,0)};o()})()</script><script>function loadDisqus(){var e,t,s=function(){this.page.url="https://www.lizheblogs.xyz/2022/03/16/Acwing/",this.page.identifier="2022/03/16/Acwing/",this.page.title="算法基础"};window.disqusReset=()=>{DISQUS.reset({reload:!0,config:s})},window.DISQUS?disqusReset():(e=document,(t=e.createElement("script")).src="https://disqus_el5qs5OXyM.disqus.com/embed.js",t.setAttribute("data-timestamp",+new Date),(e.head||e.body).appendChild(t))}{function loadOtherComment(){loadDisqus()}loadDisqus()}</script></div><script data-pjax defer src="https://cdn.jsdelivr.net/gh/sunchaser-lilu/sunchaser-cdn@master/js/circleMagic.min.js"></script><script data-pjax async src="/js/diytitle.js"></script><script data-pjax async src="//at.alicdn.com/t/font_3162155_rj0cwkyfph.js"></script><script src="//code.tidio.co/pdpo6idc0mzvfbbiob4uihzuk4wuryvn.js" async></script><script>function onTidioChatApiReady(){window.tidioChatApi.hide(),window.tidioChatApi.on("close",(function(){window.tidioChatApi.hide()}))}window.tidioChatApi?window.tidioChatApi.on("ready",onTidioChatApiReady):document.addEventListener("tidioChat-ready",onTidioChatApiReady);var chatBtnFn=()=>{document.getElementById("chat_btn").addEventListener("click",(function(){window.tidioChatApi.show(),window.tidioChatApi.open()}))};chatBtnFn()</script><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css" media="print" onload='this.media="all"'><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/gh/metowolf/MetingJS@1.2/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors=["title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"];var pjax=new Pjax({elements:'a:not([target="_blank"])',selectors:pjaxSelectors,cacheBust:!1,analytics:!1,scrollRestoration:!1});document.addEventListener("pjax:send",(function(){if(window.tocScrollFn&&window.removeEventListener("scroll",window.tocScrollFn),window.scrollCollect&&window.removeEventListener("scroll",scrollCollect),"object"==typeof preloader&&preloader.initLoading(),document.getElementById("rightside").style.cssText="opacity: ''; transform: ''",window.aplayers)for(let e=0;e<window.aplayers.length;e++)window.aplayers[e].options.fixed||window.aplayers[e].destroy();"object"==typeof typed&&typed.destroy();const e=document.body.classList;e.contains("read-mode")&&e.remove("read-mode")})),document.addEventListener("pjax:complete",(function(){window.refreshFn(),document.querySelectorAll("script[data-pjax]").forEach(e=>{const t=document.createElement("script"),o=e.text||e.textContent||e.innerHTML||"";Array.from(e.attributes).forEach(e=>t.setAttribute(e.name,e.value)),t.appendChild(document.createTextNode(o)),e.parentNode.replaceChild(t,e)}),GLOBAL_CONFIG.islazyload&&window.lazyLoadInstance.update(),"function"==typeof chatBtnFn&&chatBtnFn(),"function"==typeof panguInit&&panguInit(),"function"==typeof gtag&&gtag("config","",{page_path:window.location.pathname}),"object"==typeof _hmt&&_hmt.push(["_trackPageview",window.location.pathname]),"function"==typeof loadMeting&&document.getElementsByClassName("aplayer").length&&loadMeting(),"object"==typeof Prism&&Prism.highlightAll(),"object"==typeof preloader&&preloader.endLoading()})),document.addEventListener("pjax:error",e=>{404===e.request.status&&pjax.loadUrl("/404.html")})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><script data-pjax>function history_calendar_injector_config(){var i=document.getElementsByClassName("sticky_layout")[0];console.log("已挂载history_calendar"),i.insertAdjacentHTML("afterbegin",'<div class="card-widget card-history"><div class="card-content"><div class="item-headline"><i class="fas fa-clock fa-spin"></i><span>那年今日</span></div><div id="history-baidu" style="height: 100px;overflow: hidden"><div class="history_swiper-container" id="history-container" style="width: 100%;height: 100%"><div class="swiper-wrapper" id="history_container_wrapper" style="height:20px"></div></div></div></div>')}document.getElementsByClassName("sticky_layout")[0]&&(location.pathname,1)&&history_calendar_injector_config()</script><script data-pjax src="https://cdn.jsdelivr.net/npm/swiper/swiper-bundle.min.js"></script><script data-pjax src="https://cdn.jsdelivr.net/gh/Zfour/Butterfly-card-history/baiduhistory/js/main.js"></script><script data-pjax>function butterfly_swiper_injector_config(){var i=document.getElementById("recent-posts");console.log("已挂载butterfly_swiper"),i.insertAdjacentHTML("afterbegin",'<div class="recent-post-item" style="height: auto;width: 100%"><div class="blog-slider swiper-container-fade swiper-container-horizontal" id="swiper_container"><div class="blog-slider__wrp swiper-wrapper" style="transition-duration: 0ms;"><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/01/10/常用技巧/" alt=""><img width="48" height="48" src="https://cdn.lixingyong.com/2022/04/03/img-16446097492911a793c1631d8ef5980bc90243e5cbebd.webp" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-01-10</span><a class="blog-slider__title" href="2022/01/10/常用技巧/" alt="">学习途中小Tips</a><div class="blog-slider__text">再怎么看我也不知道怎么描述它的啦！</div><a class="blog-slider__button" href="2022/01/10/常用技巧/" alt="">详情   </a></div></div><div class="blog-slider__item swiper-slide" style="width: 750px; opacity: 1; transform: translate3d(0px, 0px, 0px); transition-duration: 0ms;"><a class="blog-slider__img" href="2022/01/01/文章Tips/" alt=""><img width="48" height="48" src="https://cdn.lixingyong.com/2022/03/22/wallhaven-28wqwg_1920x1080.webp" alt="" onerror="this.src=https://unpkg.zhimg.com/akilar-candyassets/image/loading.gif; this.onerror = null;"/></a><div class="blog-slider__content"><span class="blog-slider__code">2022-01-01</span><a class="blog-slider__title" href="2022/01/01/文章Tips/" alt="">博客常用配置</a><div class="blog-slider__text">再怎么看我也不知道怎么描述它的啦！</div><a class="blog-slider__button" href="2022/01/01/文章Tips/" alt="">详情   </a></div></div></div><div class="blog-slider__pagination swiper-pagination-clickable swiper-pagination-bullets"></div></div></div>')}for(var elist="undefined".split(","),cpage=location.pathname,epage="all",flag=0,i=0;i<elist.length;i++)cpage.includes(elist[i])&&flag++;("all"===epage&&0==flag||epage===cpage)&&butterfly_swiper_injector_config()</script><script defer src="https://unpkg.zhimg.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://unpkg.zhimg.com/hexo-butterfly-swiper/lib/swiper_init.js"></script><script data-pjax>function butterfly_clock_injector_config(){var l=document.getElementsByClassName("sticky_layout")[0];console.log("已挂载butterfly_clock"),l.insertAdjacentHTML("afterbegin",'<div class="card-widget card-clock"><div class="card-glass"><div class="card-background"><div class="card-content"><div id="hexo_electric_clock"><img class="entered loading" id="card-clock-loading" src="https://unpkg.zhimg.com/hexo-butterfly-clock/lib/loading.gif" style="height: 120px; width: 100%;" data-ll-status="loading"/></div></div></div></div></div>')}for(var elist="null".split(","),cpage=location.pathname,epage="all",flag=0,i=0;i<elist.length;i++)cpage.includes(elist[i])&&flag++;("all"===epage&&0==flag||epage===cpage)&&butterfly_clock_injector_config()</script><script src="https://pv.sohu.com/cityjson?ie=utf-8"></script><script data-pjax src="https://unpkg.zhimg.com/hexo-butterfly-clock/lib/clock.min.js"></script><script data-pjax>function butterfly_footer_beautify_injector_config(){var e=document.getElementById("footer-wrap");console.log("已挂载butterfly_footer_beautify"),e.insertAdjacentHTML("beforeend",'<div id="workboard"></div><div id="ghbdages" style="overflow:hidden;max-height:90px;height:auto;text-align:center;margin-top:10px"><div class="swiper-wrapper"><div class="swiper-slide"><a class="github-badge" target="_blank" href="https://hexo.io/" style="margin-inline:5px" title="博客框架为Hexo_v5.4.0"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/Frame-Hexo-blue.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://beian.miit.gov.cn/" style="margin-inline:5px" title="本站已在工信部备案，备案号：陕ICP备2021012694号-1"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/陕ICP备-2021012694号-A5915F.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://www.jsdelivr.com/" style="margin-inline:5px" title="本站使用JsDelivr为静态资源提供CDN加速"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/CDN-jsDelivr-orange.svg" alt=""/></a></div><div class="swiper-slide"><a class="github-badge" target="_blank" href="https://vercel.com/" style="margin-inline:5px" title="本站采用双线部署，默认线路托管于Vercel"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/Hosted-Vercel-brightgreen.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://www.upyun.com/?utm_source=lianmeng&amp;utm_medium=referral" style="margin-inline:5px" title="本站由又拍云提供CDN加速服务"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/CDN加速-又拍云-00CAFF.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://github.com/" style="margin-inline:5px" title="本站项目由Github托管"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/Source-Github-d021d6.svg" alt=""/></a></div><div class="swiper-slide"><a class="github-badge" target="_blank" href="http://creativecommons.org/licenses/by-nc-sa/4.0/" style="margin-inline:5px" title="本站采用知识共享署名-非商业性使用-相同方式共享4.0国际许可协议进行许可"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/Copyright-BY--NC--SA 4.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://www.lizheblogs.xyz/" style="margin-inline:5px" title="本战由瑶瑶同学和哲哲同学运营♥"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/哲哲和瑶瑶の小屋-正在营业-F02E65.svg" alt=""/></a><a class="github-badge" target="_blank" href="https://dash.cloudflare.com/" style="margin-inline:5px" title="本站整体由CLOUDFLARE托管并提供防护"><img src="https://npm.elemecdn.com/lz-assets@0.0.3/image/Hosted And Protect BY-CLOUDFLARE-F38020.svg" alt=""/></a></div></div></div><style>a.github-badge:hover:before {display:none}</style>')}for(var elist="null".split(","),cpage=location.pathname,epage="all",flag=0,i=0;i<elist.length;i++)cpage.includes(elist[i])&&flag++;("all"===epage&&0==flag||epage===cpage)&&butterfly_footer_beautify_injector_config()</script><script async src="https://npm.elemecdn.com/lz-assets@0.0.3/js/runtime.js"></script><script defer src="https://npm.elemecdn.com/hexo-butterfly-swiper/lib/swiper.min.js"></script><script defer data-pjax src="https://npm.elemecdn.com/hexo-butterfly-footer-beautify/lib/swiperbdage_init.min.js"></script><script data-pjax src="https://npm.elemecdn.com/hexo-filter-gitcalendar/lib/gitcalendar.js"></script><script data-pjax>function gitcalendar_injector_config(){document.getElementById("recent-posts").insertAdjacentHTML("afterbegin",'<container><style>#git_container{min-height: 290px}@media screen and (max-width:650px) {#git_container{min-height: 0px}}</style><div id="git_loading" style="width:10%;height:3%;margin:0 auto;display: block;"><svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 0 50 50" style="enable-background:new 0 0 50 50" xml:space="preserve"><path fill="#d0d0d0" d="M25.251,6.461c-10.318,0-18.683,8.365-18.683,18.683h4.068c0-8.071,6.543-14.615,14.615-14.615V6.461z" transform="rotate(275.098 25 25)"><animatetransform attributeType="xml" attributeName="transform" type="rotate" from="0 25 25" to="360 25 25" dur="0.6s" repeatCount="indefinite"></animatetransform></path></svg><style>#git_container{display: none;}</style></div><div id="git_container"></div></container>'),console.log("已挂载gitcalendar")}document.getElementById("recent-posts")&&"/"===location.pathname&&(gitcalendar_injector_config(),GitCalendarInit("https://gitcalendar.akilar.top/api?zhezheup",["#e4dfd7","#f9f4dc","#f7e8aa","#f7e8aa","#f8df72","#fcd217","#fcc515","#f28e16","#fb8b05","#d85916","#f43e06"],"zhezheup"))</script><script async src="//at.alicdn.com/t/font_2032782_8d5kxvn09md.js"></script></body></html>